A branch‐and‐bound‐based solution approach for dynamic rerouting of airborne platforms

This article is a sequel to a recent article that appeared in this journal, “An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations” [ 17 ], in which an integer programming formulation to the problem of rescheduling in‐flight assets due to changes in battlespace conditions was presented. The purpose of this article is to present an improved branch‐and‐bound procedure to solve the dynamic resource management problem in a timely fashion, as in‐flight assets must be quickly re‐tasked to respond to the changing environment. To facilitate the rapid generation of attractive updated mission plans, this procedure uses a technique for reducing the solution space, supports branching on multiple decision variables simultaneously, incorporates additional valid cuts to strengthen the minimal network constraints of the original mathematical model, and includes improved objective function bounds. An extensive numerical analysis indicates that the proposed approach significantly outperforms traditional branch‐and‐bound methodologies and is capable of providing improved feasible solutions in a limited time. Although inspired by the dynamic resource management problem in particular, this approach promises to be an effective tool for solving other general types of vehicle routing problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Bicriteria multiresource generalized assignment problem

In this study, we consider a bicriteria multiresource generalized assignment problem. Our criteria are the total assignment load and maximum assignment load over all agents. We aim to generate all nondominated objective vectors and the corresponding efficient solutions. We propose several lower and upper bounds and use them in our optimization and heuristic algorithms. The computational results have shown the satisfactory behaviors of our approaches. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 621–636, 2014     

Efficient algorithms for flexible job shop scheduling with parallel machines

Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k − 1 , and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2 .     

高精度单频信号初相测量方法

提出了一种基于误差知识的二重插值DFT方法用于高精度时钟初相测量。理论分析与数值仿真结果表明,该方法性能接近Cramer-Rao界。     

Production and transport logistics scheduling with two transport mode choices

This paper considers a new class of scheduling problems arising in logistics systems in which two different transportation modes are available at the stage of product delivery. The mode with the shorter transportation time charges a higher cost. Each job ordered by the customer is first processed in the manufacturing facility and then transported to the customer. There is a due date for each job to arrive to the customer. Our approach integrates the machine scheduling problem in the manufacturing stage with the transportation mode selection problem in the delivery stage to achieve the global maximum benefit. In addition to studying the NP‐hard special case in which no tardy job is allowed, we consider in detail the problem when minimizing the sum of the total transportation cost and the total weighted tardiness cost is the objective. We provide a branch and bound algorithm with two different lower bounds. The effectiveness of the two lower bounds is discussed and compared. We also provide a mathematical model that is solvable by CPLEX. Computational results show that our branch and bound algorithm is more efficient than CPLEX. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

基于统计性QoS保证的数据包延时界调度算法

讨论了调度算法的性能指标,对目前基于业务流的调度算法的技术特点与性能优劣进行了分析和比较.重点研究了基于时延和丢包率的算法,并提出了一种基于数据包延时界(PDB)排列的调度策略,与WFQ及传统EDF算法进行了比较,证明业务端到端超时概率随网络带宽利用率的变化性能优于传统EDF算法.     

随机弱实时系统作业调度概率保证分析

随机弱实时系统与强实时系统的显著区别是 ,它不要求实时任务的每一项作业都满足时限要求 ,只要保证作业的时限延误率低于某一阈值 ,其总体执行性能就是可以接受的。提出了概率时间需求分析法 (PTDA) ,用于估计可剥夺静态优先级调度策略下周期性任务的作业满足时限约束的概率的下界 ,并通过一个具体的实例考察了下界的紧性。对实例系统的仿真结果表明 ,PTDA分析的误差小于 1 0 % ,计算速度快 ,可以为弱实时应用的设计提供重要的参考依据     

正则化方法在拉普拉斯数值反演中的应用

本文用正则化方法给出了拉普拉斯变换的数值反演方法,并考虑了问题的不适定性,此方法在实际中有较强的应用价值.     

Cyclic best first search: Using contours to guide branch‐and‐bound algorithms

The cyclic best‐first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch‐and‐bound algorithms in a number of different settings. CBFS is a modification of best‐first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non‐empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour‐labeling functions is provided, and proof‐of‐concept computational results for mixed‐integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017     

基于熵最小化的LFM信号调频率估计算法

利用LFM信号频谱的熵随着调频率减小而降低的性质,提出了一种基于频谱熵最小化的LFM信号调频率的估计SEM方法。建立参数待估的相位补偿因子,通过搜索得到使得补偿后信号频谱熵全局最小的调频率估值。在搜索过程中,采用两级搜索策略,并引入牛顿迭代算法,有效降低了算法复杂度。理论推导和仿真结果证明,该算法为有偏算法,估计偏差量与初始频率相关,理论估计方差比较CR下界低12d B。对雷达实测回波信号进行验证,与离散多项式变换算法相比发现,提出算法估计的鲁棒性更好,并具有较高的测速精度,具有一定的应用价值。